Stirling number

In mathematics, Stirling numbers arise in a variety of analytic and combinatorics problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in his 1782 Sanpō-Gakkai (The Sea of Learning on Mathematics).

Two different sets of numbers bear this name: the Stirling numbers of the first kind and the Stirling numbers of the second kind. Additionally, Lah numbers are sometimes referred to as Stirling numbers of the third kind. Each kind is detailed in its respective article, this one serving as a description of relations between them.

A common property of all three kinds is that they describe coefficients relating three different sequences of polynomials that frequently arise in combinatorics. Moreover, all three can be defined as the number of partitions of n elements into k non-empty subsets, where each subset is endowed with a certain kind of order (no order, cyclical, or linear).

---

Notation Several different notations for Stirling numbers are in use. Ordinary (signed) Stirling numbers of the first kind are commonly denoted:

$s(n,k)\backslash ,.$

Unsigned Stirling numbers of the first kind, which count the number of of n elements with k disjoint cycles, are denoted:

$\backslash biggl\{n\; =c(n,k)=|s(n,k)|=(-1)^\{n-k\}\; s(n,k)\backslash ,$

Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets:Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Concrete Mathematics, Addison-Wesley, Reading MA. , p. 244.

$\backslash biggl\backslash \backslash$ for the falling factorial and $\backslash \; x^\{\backslash overline\{n\}\}\backslash$ for the rising factorial are also often used.

Martin Aigner (2025). 9783540390329, Springer. . ISBN 9783540390329

(Confusingly, the Pochhammer symbol that many use for falling factorials is used in for rising factorials.)

Similarly, the rising factorial, defined as $\backslash \; x^\{(n)\}\backslash \; =\backslash \; x(x+1)\backslash \; \backslash cdots(x+n-1)\backslash \; ,$ is a polynomial in of degree whose expansion is

$x^\{(n)\}\backslash \; =\backslash \; \backslash sum\_\{k=0\}^n\backslash \; \backslash biggl\{n\backslash \; x^k\backslash \; =\backslash \; \backslash sum\_\{k=0\}^n\backslash \; (-1)^\{n-k\}\backslash \; s(n,k)\backslash \; x^k\backslash \; ,$

with unsigned Stirling numbers of the first kind as coefficients. One of these expansions can be derived from the other by observing that $\backslash \; x^\{(n)\}\; =\; (-1)^n\; (-x)\_\{n\}\; ~.$

Stirling numbers of the second kind express the reverse relations:

$\backslash \; x^n\backslash \; =\backslash \; \backslash sum\_\{k=0\}^n\backslash \; S(n,k)\backslash \; (x)\_k\backslash$

and

$\backslash \; x^n\backslash \; =\backslash \; \backslash sum\_\{k=0\}^n\backslash \; (-1)^\{n-k\}\backslash \; S(n,k)\backslash \; x^\{(k)\}\; ~.$

---

As change of basis coefficients Considering the set of in the (indeterminate) variable x as a vector space, each of the three sequences

$x^0,x^1,x^2,x^3,\backslash dots\; \backslash quad\; (x)\_0,(x)\_1,(x)\_2,\backslash dots\; \backslash quad\; x^\{(0)\},x^\{(1)\},x^\{(2)\},\backslash dots$

is a basis. That is, every polynomial in x can be written as a sum $a\_0\; x^\{(0)\}\; +\; a\_1\; x^\{(1)\}\; +\; \backslash dots\; +\; a\_n\; x^\{(n)\}$ for some unique coefficients $a\_i$ (similarly for the other two bases). The above relations then express the change of basis between them, as summarized in the following commutative diagram:

The coefficients for the two bottom changes are described by the Lah numbers below. Since coefficients in any basis are unique, one can define Stirling numbers this way, as the coefficients expressing polynomials of one basis in terms of another, that is, the unique numbers relating $x^n$ with falling and rising factorials as above.

Falling factorials define, up to scaling, the same polynomials as binomial coefficients: $\backslash binom\{x\}\{k\}\; =\; (x)\_k/k!$. The changes between the standard basis $\backslash textstyle\; x^0,\; x^1,\; x^2,\; \backslash dots$ and the basis $\backslash binom\{x\}\{0\},\; \backslash binom\{x\}\{1\},\; \backslash binom\{x\}\{2\},\; \backslash dots$ are thus described by similar formulas:

$x^n=\backslash sum\_\{k=0\}^n\; \backslash biggl\backslash \{k+1\}$

This can be proved by induction.

For example, the sum of fourth powers of integers up to n (this time with n included), is:

$\backslash begin\{align\}$

\sum_{i=0}^{n} i^4 & = \sum_{i=0}^n \sum_{k=0}^4 \biggl\

Post Comment